package com.company.algo.tree;

import com.company.algo.pojo.TreeNode;

/**
 * 力扣第 654 题
 * 构造最大二叉树
 * 按照题目给出的例子，输入的数组为[3,2,1,6,0,5]，对于整棵树的根节点来说，其实在做这件事：
 * TreeNode constructMaximumBinaryTree([3,2,1,6,0,5]) {
 * // 找到数组中的最大值
 * TreeNode root = new TreeNode(6);
 * // 递归调用构造左右子树
 * root.left = constructMaximumBinaryTree([3,2,1]);
 * root.right = constructMaximumBinaryTree([0,5]);
 * return root;
 * }
 * 对于每个根节点，只需要找到当前nums中的最大值和对应的索引，然后递归调用左右数组构造左右子树即可。
 */
public class ConstructMaximumBinaryTree {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int lo, int hi) {
        //base case
        if (lo > hi) return null;
        //找到数组中的最大值和对应索引
        int idx = -1, maxVal = -1;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                idx = i;
            }
        }
        //递归调用构造左右子树
        TreeNode root = new TreeNode(maxVal);
        root.left = build(nums, lo, idx - 1);
        root.right = build(nums, idx + 1, hi);
        return root;
    }
}
